#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include "utils.h"
using namespace std;

class Solution {
public:
    void flatten(TreeNode *root) {
        if (root == NULL) return;
        do_flatten(root);
    }

    TreeNode *do_flatten(TreeNode *root) {
        if (root->left == NULL && root->right == NULL) return root;
        if (root->left == NULL) return do_flatten(root->right);

        TreeNode *tail = do_flatten(root->left);
        tail->right = root->right;
        root->right = root->left;
        root->left = NULL;
        if (tail->right == NULL) return tail;
        else return do_flatten(tail->right);
    }
};

int main(int argc, char *argv[])
{
    int level_order[] = {1,2,5,3,4,-1,6};
    vector<int> v(level_order, level_order+sizeof(level_order)/sizeof(int));
    TreeNode *root = build_binary_tree(v);

    Solution ss;
    ss.flatten(root);
    print_vector(levelOrder(root));

    ss.flatten(root);
    print_vector(levelOrder(root));

    return 0;
}
